﻿//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//L0 → L1 → … → Ln - 1 → Ln
//请将其重新排列后变为：
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//输入：head = [1, 2, 3, 4]
//输出：[1, 4, 2, 3]
//
//输入：head = [1, 2, 3, 4, 5]
//输出：[1, 5, 2, 4, 3]
//
//提示：
//	链表的长度范围为[1, 5 * 10^4]
//	1 <= node.val <= 1000

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        // 处理边界情况

        if (head == nullptr || head->next == nullptr ||
            head->next->next == nullptr)
            return;
        // 1.找到链表的中间节点-快慢双指针（⼀定要画图考虑slow的落点在哪⾥）

        ListNode* slow = head, * fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2.把slow后⾯的部分给逆序-头插法

        ListNode* head2 = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr; // 注意把两个链表给断开

        while (cur) {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        // 3.合并两个链表-双指针

        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        ListNode* cur1 = head, * cur2 = head2->next;
        while (cur1) {
            // 先放第⼀个链表

            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
            // 再放第⼆个链表

            if (cur2) {
                prev->next = cur2;
                prev = prev->next;
                cur2 = cur2->next;
            }
        }
        delete head2;
        delete ret;
    }
};